一.最大流问题
1.P2764 最小路径覆盖问题
首先每个点用一条边覆盖,为了使路径尽可能少,我们要连接一些路径。
将每个点拆成两个点 ,对于 这条边,连接 并将容量设为 ,如果这条边有流则表示将 的路径合并。
然后连接 ,容量也设为 (要求顶点不相交,每个点只能连接一次)
最后图的最大流便是连接的最大数量,答案为 。
方案直接记录后继节点就可以了。
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define Inf 0x3f3f3f3f
const int MAXN = 300 , MAXM = 7000;
struct node {
int v , flow , nxt;
}Graph[ 2 * MAXM + 5 ];
int tot = 1 , Head[ MAXN + 5 ];
void Add_Edge( int u , int v , int f ) {
Graph[ ++ tot ] = { v , f , Head[ u ] };
Head[ u ] = tot;
}
int n , m , s , t;
int lev[ MAXN + 5 ] , cur[ MAXN + 5 ] , nxt[ MAXN + 5 ] , sta[ MAXN + 5 ];
bool Layering( int s , int t ) {
memset( lev , -1 , sizeof( lev ) );
memcpy( cur , Head , sizeof( Head ) );
queue< int > Que;
Que.push( s ) , lev[ s ] = 0;
while( !Que.empty( ) ) {
int u = Que.front( ); Que.pop( );
for( int i = Head[ u ] ; i ; i = Graph[ i ].nxt ) {
int v = Graph[ i ].v , flw = Graph[ i ].flow;
if( flw > 0 && lev[ v ] == -1 )
lev[ v ] = lev[ u ] + 1 , Que.push( v );
}
}
return lev[ t ] != -1;
}
int dfs( int u , int t , int f ) {
if( u == t ) return f;
for( int i = cur[ u ] ; i ; i = Graph[ i ].nxt ) {
int v = Graph[ i ].v , flw = Graph[ i ].flow;
cur[ u ] = i;
if( flw > 0 && lev[ u ] < lev[ v ] ) {
int mf = dfs( v , t , min( f , flw ) );
if( mf ) {
Graph[ i ].flow -= mf; Graph[ i ^ 1 ].flow += mf;
if( u != s && v > n ) sta[ v - n ] = 1;
nxt[ u ] = v;
return mf;
}
}
}
return 0;
}
int Dinic( int s , int t ) {
int Maxf = 0;
while( Layering( s , t ) ) for( int fl ; ( fl = dfs( s , t , Inf ) ) > 0 ; Maxf += fl );
for( int i = 1 ; i <= n ; i ++ )
if( !sta[ i ] ) {
printf("%d", i );
int u = i;
while( nxt[ u ] && nxt[ u ] != t ) {
printf(" %d", nxt[ u ] - n );
u = nxt[ u ] - n;
}
printf("\n");
}
return Maxf;
}
int main( ) {
scanf("%d %d",&n,&m);
s = 2 * n + 1 , t = 2 * n + 2;
for( int i = 1 , u , v ; i <= m ; i ++ ) {
scanf("%d %d",&u,&v);
Add_Edge( u , v + n , 1 );
Add_Edge( v + n , u , 0 );
}
for( int i = 1 ; i <= n ; i ++ )
Add_Edge( s , i , 1 ) , Add_Edge( i , s , 0 );
for( int i = 1 ; i <= n ; i ++ )
Add_Edge( i + n , t , 1 ) , Add_Edge( t , i + n , 0 );
printf("%d\n", n - Dinic( s , t ) );
return 0;
}